מושגי בסיס בקריפטוגרפיה -
מיהם עליזה, בני וחווה?

אור דונקלמן,
מועדון הלינוקס החיפאי, 13/12/2004

קריפטוגרפיה

2

כל הזכויות שמורות © All rights reserved

מדע ההגנה על מידע

מטרתה הבסיסית היתה הסתרת מידע, משמע לדאוג שעליזה (Alice) ובני (Bob), בעלי סוד משותף, יוכלו להעביר ביניהם מידע שרק הם יבינו, בלי שחווה (Eve) שמאזינה להם תבין.

עם הזמן, הורחבה המטרה וכיום היא כול	לת גם הגנה כנגד שינוי תוכן המידע, התחזות למקור המידע ועוד...

מועדון הלינוקס החיפאי

פונקציות קריפטוגרפיות

1

כל הזכויות שמורות © All rights reserved

צפנים:

צפני מפתח משותף (סודי, פרטי, סימטרי)

צפני מפתח פומבי (אסימטרי)

חתימות דיגיטלית

MAC: Message Authentication Codes

פונקציות תמצות (hash) קריפטוגרפיות

פרוטוקולים להסכמה על מפתחות

פרוטוקולי הזדהות קריפטוגרפיים

הוכחות באפס מידע (Zero Knowledge Proofs)

חישוב בטוח (Secure Multi-Party Computation)

פרוטוקולי הצבעה, כסף אלקטרוני, סכימות חלוקת סוד, הצפנה קוונטית, ועוד ...

מועדון הלינוקס החיפאי

צפנים

1

כל הזכויות שמורות © All rights reserved

המטרה: שמירה על סודיות המידע

שליחת הודעה דרך ערוץ ציבורי כך שרק הגורמים המורשים יוכלו להבין את תוכנה.

שמירת מידע רגיש (לדוגמא, קוד המקור של חלונות) במחשב במקום לא בטוח (שרת ציבורי), כך שהגורמים הלא מורשים לא יוכלו להבין את המידע.

שמירת מידע רגיש במחשב, שאמור להשאר בטוח גם לאחר פריצה למחשב.

צופן מורכב מאלגוריתם הצפנה ואלגוריתם פענוח

מועדון הלינוקס החיפאי

צפנים (המשך)

1

כל הזכויות שמורות © All rights reserved

הרעיון: אחד המשתתפים לוקח טקסט (כתב גלוי – plaintext) אותו הוא רוצה להסתיר, ומבצע עליו פעולת הצפנה. פעולת ההצפנה מתבצעת בעזרת מפתח הצפנה מתאים. לתוצאת ההצפנה קוראים כתב סתר - ciphertext.

מי שיש בידיו מפתח הפענוח המתאים, ורק הוא, יכול לגלות מהו הכתב הגלוי מתוך כתב הסתר. זאת נעשה ע"י פעולת הפענוח של כתב הסתר בעזרת מפתח הפענוח.

מועדון הלינוקס החיפאי

צפנים - סימונים

1

כל הזכויות שמורות © All rights reserved

M – ההודעה הגלויה, Plaintext, כתב גלוי

C – ההודעה המוצפנת, Ciphertext, כתב סתר

ke – מפתח ההצפנה

kd – מפתח הפענוח

E – פונקצית ההצפנה

D – פונקצית הפענוח

חייב להתקיים כי אם ke ו kd מפתחות ההצפנה והפענוח המתאימים אזי

C=Eke(M)

M=Dkd(C)

M=Dkd (Eke(M))

מועדון הלינוקס החיפאי

עקרון קרכהוף

1

כל הזכויות שמורות © All rights reserved

ישנה הנחה קריפטוגרפית (שמופיעה גם בהקשר של אבטחה) – שיטת ההצפנה ידועה. הדבר שאיננו ידוע הוא המפתח שבו השתמשו להצפנה.

ההנחה שהצופן ידוע ופיסת המידע היחידה שחסרה למתקיף היא המפתח שהשתמשו בו להצפנה, מוכרת כ”עקרון קרכהוף”.

מערכת שבטוחה גם כאשר השיטה ידועה, בטוחה גם כאשר השיטה איננה ידועה. ההפך איננו נכון!

מועדון הלינוקס החיפאי

צופן מושלם – מפתח חד-פעמי

1

כל הזכויות שמורות © All rights reserved

צופן מפתח חד-פעמי (One Time Pad) הינו צופן מושלם – צופן שאף כוח חישובי אינו מסוגל לפרוץ. אורך המפתח k הוא כאורך ההודעה M שברצוננו להצפין.

פעולת ההצפנה היא ביט אחר ביט, ואנו מבצעים XOR בין ההודעה למפתח. הפענוח הוא ביצוע XOR שוב עם המפתח:

M

C

k

A

מאזינים

C

M

k

B

מועדון הלינוקס החיפאי

בטיחות מושלמת וחישובית

1

כל הזכויות שמורות © All rights reserved

נאמר שצופן הוא Unconditionally Secure (בטוח באופן מושלם), אם בהינתן אינסוף משאבים, ומספר אינסופי של זוגות של הודעות חשופות ומוצפנות, לא ניתן למצוא plaintext בהנתן ה-ciphertext הבא.

מכיוון שצפנים כאלה אינם מעשיים, לא נדרוש Unconditional Security, אלא נסתפק ב-Computational Security (בטיחות חישובית). דרישה זו היא מעשית יותר.

מועדון הלינוקס החיפאי

בטיחות מושלמת וחישובית (המשך)

1

כל הזכויות שמורות © All rights reserved

בכל האלגוריתמים בהם משתמשים היום (האלגוריתמים ה"מעשיים"), או שאורך המפתח הרבה יותר קטן מאורך ההודעה, או שמצפינים הרבה הודעות עם אותו מפתח.

אם נתון כוח חישוב בלתי מוגבל, ניתן לשבור את כל הצפנים ה"מעשיים", על ידי ביצוע חיפוש ממצה (exhaustive search) על מרחב המפתחות.

לכן נדרוש שמספר המפתחות האפשריים יהיה גדול דיו – לדוגמא 2128 מפתחות אפשריים.

מועדון הלינוקס החיפאי

בטיחות חישובית

1

כל הזכויות שמורות © All rights reserved

אלגוריתם הצפנה יקרא computationally secure (בטוח חישובית) אם קשה מאד לשחזר את הטקסט המקורי בהינתן הטקסט המוצפן (למשל, הזמן הדרוש לכך ארוך מדי).

לגבי אף אלגוריתם בו משתמשים היום, לא קיימת הוכחה של קושי פיצוח (אומנם חלק מהם מסתמכים על הנחות מתמטיות סבירות).

בהיעדר הוכחה לבטיחות, צופן נחשב חזק אם הרבה זמן לא הצליחו לשבור אותו.

מועדון הלינוקס החיפאי

התקפות על צפנים

1

כל הזכויות שמורות © All rights reserved

בהנתן צופן E שאנו רוצים לתקוף, ניתן לבצע התקפות רבות:

פענוח כתבי הסתר

גילוי המפתח שהשתמשו בו להצפנה

“הצפנת” הודעות נוספות (גם ללא ידיעת המפתח)

ישנם מודלים שונים להתקפה, אך כולם מניחים ידיעה של:

אלגוריתם ההצפנה

איפיון סטיסטי של ההודעות הגלויות (לדוגמא – כל ההודעות הן באנגלית). כלומר, תוקף מסוגל לדעת אם הודעה היא “הגיונית”

מועדון הלינוקס החיפאי

התקפות על צפנים (המשך)

1

כל הזכויות שמורות © All rights reserved

התקפת Ciphertext Only:

לתוקף קבוצת כתבי סתר {C}.

לרוב התוקף ינסה להשיג את הכתבים הגלויים המתאימים.

התקפת Known plaintext:

לתוקף קבוצת זוגות של כתבי סתר והכתבים הגלויים שלהם {(P,C)}.

לרוב התוקף ינסה להשיג את המפתח, או להיות מסוגל להצפין ולפענח הודעות שאינן בקבוצת ההודעות שהוא מכיר.

דוגמא: חיפוש ממצה (Exhaustive Search)

מועדון הלינוקס החיפאי

התקפות על צפנים (המשך)

1

כל הזכויות שמורות © All rights reserved

התקפת Chosen Plaintext:

התוקף בוחר קבוצת כתבים גלויים {P} ומבקש מהמותקף להצפין לו אותם תחת המפתח הלא ידוע.

בהנתן קבוצת כתבי הסתר, לרוב התוקף ינסה להשיג את המפתח.

דוגמא: Differential Cryptanalysis

התקפת Adaptive Chosen Plaintext:

התוקף מבקש הצפנה של קבוצת הודעות, מקבל את כתבי הסתר, מבקש הצפנה של קבוצות הודעות נוספות (על סמך מה שקיבל) וכן הלאה.

מועדון הלינוקס החיפאי

צפני בלוקים

1

כל הזכויות שמורות © All rights reserved

צופן בלוקים מקבל קלט בגודל נתון (גודל הבלוק) יחד עם מפתח סודי ומצפין אותו להודעה בגודל נתון (לרוב אותו הגודל).

בכדי להצפין הודעה M, שאורכה עולה על אורך הקלט של הצופן, מחלקים את M לבלוקים שאורכם כאורך הקלט של הצופן (אם יש צורך מבצעים דיפון). כל בלוק עובר הצפנה בנפרד.

ניתן להצפין כל בלוק על סמך בלוקים קודמים או באופן בלתי תלוי. הקשר בין הצפנת בלוקים עוקבים נקרא Mode of Operation.

מועדון הלינוקס החיפאי

צפני בלוקים (המשך)

1

כל הזכויות שמורות © All rights reserved

תהי M הודעת הקלט המחולקת לבלוקים M=M1M2…Mn

ניתן להצפין כל בלוק באופן בלתי תלוי בבלוקים קודמים על ידי שימוש באותו מפתח k. מוד הפעולה הזה נקרא Elctronic Code Book ומתקיים: (Ci=Ek(Mi

ישנם צפני בלוקים רבים. בין הנפוצים בשימוש: AES,DES,IDEA.

מועדון הלינוקס החיפאי

Data Encryption Standard (DES)

1

כל הזכויות שמורות © All rights reserved

פותח ע”י I.B.M. בשנות ה70- אומץ ע”י NIST.

גודל בלוק – 64 סיביות

אורך המפתח – 56 סיביות

התקן היה בשימוש נרחב מאז במשך למעלה מ25- שנה.

במשך תקופה ארוכה אורך המפתח הקצר היווה נקודה חלשה של DES.

החל משנת 1997 נערכו DES Challenges – תחרויות בהן מפורסם כתב גלוי וכתב סתר מתאים שהוצפנו תחת מפתח לא ידוע. מטרת האתגר – זיהוי המפתח ששימש להצפנה.

מועדון הלינוקס החיפאי

DES Challenges

1

כל הזכויות שמורות © All rights reserved

האתגר הראשון שוחרר בפברואר 1997. אחרי ארבעה חודשי עבודה (של 78,000 מחשבים דרך האינטרנט) נמצא המפתח.

האתגר השני שוחרר בינואר 1998. באמצעות קבוצת distributed.net תוך 39 יום נמצא המפתח.

האתגר השלישי שוחרר ביוני 1998. קבוצת Electronic Frontier Foundation תכננה מכונה בעלות כוללת של 210,000$ (תכנון+בניה בפועל) שמצאה את המפתח המבוקש תוך 56 שעות.

אתגר נוסף ששוחרר ביולי 1998 נפתר תוך 22 שעות ע”י שיתוף פעולה בין EFF ו-distributed.net.

מועדון הלינוקס החיפאי

Advanced Encryption Standard (AES)

1

כל הזכויות שמורות © All rights reserved

לנוכח אורך המפתח הקצר, וחוסר היעילות של DES הוחלט ב-NIST כי הגיע הזמן להחליפו. ב-1997 פנה הארגון לקהילה הקריפטוגרפית בבקשה להציע הצעות ל-AES.

15 הצעות הוגשו – ומתוכן 5 נבחרו לשלב ניתוח מעמיק:

MARS

RC6

Rijndael

Serpent

Twofish

מועדון הלינוקס החיפאי

Rijndael (AES)

1

כל הזכויות שמורות © All rights reserved

בשנת 2000 הוכרז Rijndael כסטדנרט ההצפנה החדש, ובשנת 2001 יצא הסטדנרט באופן סופי.

גודל הבלוק – 128 סיביות

אורך המפתח – 128, 192 או 256 סיביות

יעילות בתוכנה (מימוש על Pentium דורש בערך 20 מחזורי שעון לצורך הצפנת byte)

יעילות בחומרה

ל-Rijndael מספר סיבובים משתנה (בין 10 ל14-) בהתאם לאורך המפתח. ההתקפה התיאורטית הכי טובה הידועה עליו היא כנגד 7 שלבים.

מועדון הלינוקס החיפאי

צפני שטף (Stream Ciphers)

1

כל הזכויות שמורות © All rights reserved

צפני שטף הינם צפנים המיועדים לשימוש במקרים בהם המידע מגיע בשטף – לדוגמא, שיחת טלפון. במקרה זה מצפינים “בלוקים” קטנים (1,2,4 או 8 סיביות).

באופן עקרוני, צפנים אלה מהירים יותר מצפני בלוקים אך נחשבים לבטוחים הרבה פחות.

ההצפנה מבוססת לא רק על המידע המוצפן כרגע והמפתח, אלא גם על מספר הבלוק, ערכי הבלוק(ים) הקודם(ים), ועוד.

ישנם צפני שטף רבים, אך רובם נפרצו ונחשבים כלא בטוחים. בתהליך דומה לתהליך ה-AES הוצעו כ7- צפני שטף כהצעה לסטנדרט ע”י טובי מתכנני צפני השטף. שנה וחצי לאחר קבלת ההצעות כולם נפרצו.

מועדון הלינוקס החיפאי

דוגמא לצופן שטף - RC4

1

כל הזכויות שמורות © All rights reserved

צופן השטף RC4 נחשב כסטנדרט דה-פקטו. זאת על אף העובדה שיש לו בעיות בטיחות רבות, והיותו של הצופן סוד מסחרי.

בהנתן מפתח k (באורך של עד 256 בתים), הצופן עובר איתחול, ולאחריו פולט רצף סיביות פסואדו-אקראי המשמש מפתח למעין One Time Pad.

הצפנה (ופענוח) – ביצוע XOR בין המפתח שיצא והמידע.

M

C

k

A

RC4

M

B

k

RC4

מועדון הלינוקס החיפאי

צפני מפתח פומבי

צפני מפתח פומבי

1

כל הזכויות שמורות © All rights reserved

לכל משתמש יש זוג מפתחות:

- מפתח פומבי המשמש להצפנה

- מפתח פרטי המשמש לפענוח והידוע רק למשתמש

בהנתן מפתח ההצפנה קשה (חישובית) למצוא את מפתח הפענוח

רוב הצפנים הללו מבוססים על ההנחה שקיימות בעיות מתמטיות שקל מאוד לפתור בהנתן מידע מסוים וקשה אחרת (trapdoor functions). לדוגמא, שיטת RSA שנציג מיד מבוססת על בעיית פירוק לגורמים ראשוניים של מספר פריק גדול (factoring)

מועדון הלינוקס החיפאי

צפני מפתח פומבי (המשך)

1

כל הזכויות שמורות © All rights reserved

צפני מפתח פומבי הם מעין תיבת דואר מאובטחת:

כל אחד יכול לשלשל מעטפה אל התיבה, ורק בעליה של התיבה מסוגל למצוא מה נשלח אליו.

במציאות, כדי להשיג תכונות בטיחות חזקות יותר, משתמשים בצפני מפתח פומבי באופן די שונה ממה שנראה היום. עם זאת, העקרונות הם זהים, ומשתמשים באותן פונקציות הצפנה שנראה.

מועדון הלינוקס החיפאי

RSA

1

כל הזכויות שמורות © All rights reserved

RSA ראשי התיבות של ממציאיו Rivest, Shamir

ו-Adelman, הינו צופן המפתח הפומבי הראשון שהוצע (שנת 1978). מפתחיו כובדו בפרס טיורינג בשנת 2004 על הפיתוח.

המפתח הפומבי של המשתמש הוא זוג מספרים שלמים (n,e), כאשר n הינו המודולו בו מתבצעים החישובים ו-e הוא המעריך (אקספוננט) הפומבי המשמש להצפנה:

עבור הודעה m המקיימת n>m>0

c=me (mod n)

מועדון הלינוקס החיפאי

RSA

1

כל הזכויות שמורות © All rights reserved

המפתח הפרטי של המשתמש הוא מספר שלם, המכונה המעריך הפרטי – d. את ערך המודולו ניתן לקחת מהמפתח הפומבי או להתייחס אליו כחלק מהמפתח הפרטי. עבור כתב סתר c המקיים n>c>0 הפענוח הינו:

m=cd (mod n)

מועדון הלינוקס החיפאי

דרישות מ-RSA

1

כל הזכויות שמורות © All rights reserved

ברור שחייבים להתקיים כל מיני קשרים בין n,e

ו-d. נרצה שיתקיימו התנאים הבאים:

פענוח הודעה מוצפנת ייתן את ההודעה המקורית, כלומר שיתקיים

(me)d (mod n)= m

בהנתן n,e קשה למצוא את d.

המשתמש החוקי (בעל המפתח) כן יהיה מסוגל למצוא את d.

מועדון הלינוקס החיפאי

RSA

1

כל הזכויות שמורות © All rights reserved

יצירת מפתחות:

בחר זוג ראשוניים גדולים (512 סיביות או יותר) p,q.

מצא זוג מספרים e,d כך ש-((ed=1(mod (p-1)(q-1.

פרסם את (n,e) כמפתח פומבי ושמור את d כפרטי.

הצפנה של הודעה m נעשית ע"י העלאת ההודעה בחזקת e מודולו n:

הפענוח של כתב סתר c נעשה ע”י העלאת כתב הסתר בחזקת d מודולו n:

כמובן שמתקיים:

D(E(M))=D(me (mod n))= med (mod n)=m

E(D(M))=E(md (mod n))= med (mod n)=m

c=me (mod n)

m=cd (mod n)

מועדון הלינוקס החיפאי

בטיחות RSA

1

כל הזכויות שמורות © All rights reserved

הקושי של RSA מסתמך על הקושי של מציאת d ללא ידיעת הפירוק לגורמים ראשוניים של n. בעיה זו נקראת בעית RSA:

קלט: (e,n)

פלט: d המקיים ((ed=1(mod (p-1)(q-1.

ברור כי מי שיודע לפתור את בעית הפירוק לגורמים ראשונים (factoring) מסוגל לפתור גם את הבעיה הזו, אם כי יתכן שניתן לשבור את RSA גם ללא פירוק.

בעית הפירוק נחקרת כבר שנים (עוד לפני שהקריפטוגרפים גזלו אותה מאנשי המחקר התיאורטי של תורת המספרים), אך עד היום הבעיה נחשבת קשה.

מועדון הלינוקס החיפאי

פירוק לגורמים – מאז ועד היום

1

כל הזכויות שמורות © All rights reserved

RSA-129 הינו מספר בן 129 ספרות (426 סיביות), אשר פורסם ב1977-.

פורק לגורמים ב1994- ע”י שימוש ב1600- מחשבים (דרך ה-Internet), תוך שמונה חודשים.

היום, אלגוריתם הפירוק הטוב ביותר יכול לפרק מספר באורך 512 סיביות במספר ימים תוך שימוש בעשרות מחשבים וחומרה ייעודית בעלות משוערכת של 10 מיליון דולר.

כיום, באופן מעשי, לא ניתן לפרק לגורמים ראשוניים מספרים בני 1024 סיביות או יותר.

מועדון הלינוקס החיפאי

צפנים – הערה לסיכום

1

כל הזכויות שמורות © All rights reserved

צפנים נועדו להבטיח את סודיות המידע בלבד! הם אינם מבטיחים את שלמותו של המידע.

לדוגמא, בצופן RC4 החלפת ביט בכתב הסתר מחליפה את ערך הביט בכתב המפוענח. במיוחד כאשר ידוע לנו חלק מהמידע המוצפן, יש לנו יכולת לשלוט במה יפוענח.

לפיכך חשוב להשתמש באמצעים המבטיחים שלמות, דוגמת MAC וחתימה דיגטלית, שיבטיחו שהמידע לא שונה.

מועדון הלינוקס החיפאי

אימות ושלמות -
חתימות דיגטליות ו-MAC

מהו אימות?

כל הזכויות שמורות © All rights reserved

אימות הוא תהליך באמצעותו ניתן לוודא בנוגע למידע מסוים את:

זהות השולח (Identity)

שלמות המידע (Integrity)

פירוש הדבר הוא כי המידע הגיע ממקום ידוע, ולא שונה בדרך.

1

מועדון הלינוקס החיפאי

אימות באמצעים קריפטוגרפיים

כל הזכויות שמורות © All rights reserved

קיימים שני סוגים של פרימטיביים קריפטוגרפיים לביצוע אימות:

מבוססי מפתחות פומביים – חתימות דיגטליות (אלקטרוניות) Digital Signatures.

מבוססי מפתח משותף – Message Authentication Codes.

שני סוגי הפרימטיביים מספקים אימות מקור השולח, כאשר לרוב חתימות דיגטליות מספקות גם הגנה על שלמות ההודעה (MAC תמיד שומר על שלמות).

תכונה נוספת שיש לחתימות דיגטליות (ואין ל-MAC) היא אי-הכחשה (Non-repudiation).

1

מועדון הלינוקס החיפאי

אלגוריתמי חתימה דיגטלית

כל הזכויות שמורות © All rights reserved

חתימה דיגטלית מבוססת על מפתח פומבי. לפני שמשתמש U חותם על מסמכים הוא מפרסם את PubU המפתח הפומבי שלו. במקביל הוא שומר אצלו את המפתח הפרטי שלו PrU.

שיטת חתימה דיגטלית היא בעצם זוג אלגוריתמים:

אלגוריתם חתימה – (sig=S(M,Pr U כאשר sig היא החתימה.

אלגוריתם בדיקה – V(M,sig,PubU)=true/false האלגוריתם מחזיר true אם החתימה sig על הודעה M נוצרה ע”י U או false אחרת.

זוג (M,sig) עבורו אלגוריתם הבדיקה מחזיר true נקרא זוג חוקי (או לגיטימי).

1

מועדון הלינוקס החיפאי

דרישות מאלגוריתמי חתימה דיגטלית

כל הזכויות שמורות © All rights reserved

דרישות מאלגוריתם החתימה:

בהנתן M ו-PrU קל לחשב את (S(M,PrU

בהנתן PubU קשה לחשב מתוכו את PrU

ללא ידיעת PrU קשה למצוא זוגות (igM,s) כך ש-V(M,sig,PubU)=true

בהנתן סט גדול של זוגות {(M,sig)} ו-PubU קשה לייצר זוג (M,sig) חוקי שאיננו בסט

הדרישות הנ”ל מציגות את מה שאנו דורשים במציאות מחתימות - אדם מסוים U הוא היחיד המסוגל לחתום בשמו. אדם אחר לא יצליח לזייף חתימה של U, גם אם יש לו הרבה חתימות קיימות של האדם.

1

מועדון הלינוקס החיפאי

חתימה דיגטלית - המשך

כל הזכויות שמורות © All rights reserved

נהוג כי ההודעה החתומה היא שרשור ההודעה המקורית m והחתימה sig, כלומר m||sig.

לנוכח הדרישות הנ”ל, חתימה דיגטלית מספקת:

אותנטיקציה (אימות) זהות חותם ההודעה, מכיוון שהוא היחידי שמסוגל לייצר חתימה.

אי הכחשה - מכיוון שהחותם הוא היחיד המסוגל לייצר את החתימה (הוא הבעלים היחיד של PrU ), קיום חתימה חוקית מעיד כי הוא חתם על ההודעה.

שלמות – שינוי ההודעה מחייב שינוי החתימה (עקב הדרישות הנ”ל).

1

מועדון הלינוקס החיפאי

חתימה דיגטלית - המשך

כל הזכויות שמורות © All rights reserved

ישנן מספר רב של שיטות חתימה דיגטלית. לכל אחת מהן בסיס מתמטי שונה, והנחות אחרות. כמו עבור צפני מפתח פומבי, אין לאף שיטת חתימה הוכחה מלאה כי היא עומדת בדרישות שהזכרנו.

בין השיטות הנפוצות והידועות:

El-Gamal: מבוססת על בעיית הלוגריתם הדיסקרטי שנראה בהמשך. אורך החתימה הוא בד”כ 1024 סיביות.

(Digital Signature Algorithm (DSA: עיבוד של NIST לשיטה של El-Gamal. אורך החתימה – 320 סיביות.

ECDSA: גרסא של ה-DSA המבוססת על עקומות אלפיטיות.על אף אורך החתימה הזהה של 320 סיביות, השיטה נחשבת הרבה יותר בטוחה מ-DSA.

1

מועדון הלינוקס החיפאי

חתימה דיגטלית - דוגמא

כל הזכויות שמורות © All rights reserved

לפני הדוגמא עצמה, נקדים ונזהיר שזוהי דוגמא בעייתית. השימוש ב-RSA לצורך חתימות הוא טריקי, ויש לעשותו תוך שימוש במנגנונים הנכונים (שהם הרבה יותר מורכבים ממה שנראה כעת).

באתחול, המשתמש בוחר לעצמו מפתח RSA פומבי כמו בהצפנה – (n,e) ושומר לעצמו את המפתח הפרטי המתאים d.

לצורך חתימה על הודעה m, המשתמש מחשב

הבדיקה של הודעה חתומה (m,sig) היא האם

1

sig=md (mod n)

m=sige (mod n)

מועדון הלינוקס החיפאי

חתימה דיגטלית – המשך דוגמא

כל הזכויות שמורות © All rights reserved

מכיוון שרק המשתמש יודע את d הרי שהוא היחידי שיכול לחתום.

המפתח הציבורי (n,e) ידוע לכל העולם, שמסוגל לאמת את החתימה.

ניתן להראות כי מי שמסוגל לייצר חתימה על הודעה נתונה m מסוגל גם לפענח הודעות שהוצפנו תחת המפתח הפומבי של המשתמש.

עם זאת יש לחתימות בשיטה הנ"ל מספר בעיות עיקריות. החמורה ביותר בינהן היא היכולת לייצר זוגות הודעה-חתימה “לגיטמיות” ללא ידיעת המפתח הפרטי.

ישנן דרכים שונות לשימוש ב-RSA כבסיס לשיטת חתימה, כאשר הנפוצה והבטוחה בין השיטות נקראת RSA-PSS.

1

מועדון הלינוקס החיפאי

בעיות של פונקציות חתימה דיגטליות

כל הזכויות שמורות © All rights reserved

שימוש בחתימה דיגיטלית מגדיל את גודל הנתונים שיש להעביר

זמן חישוב החתימה הדיגיטלית ארוך מאוד ותלוי באורך ההודעה (זוהי קריפטוגרפיית מפתח פומבי)

זמן הבדיקה של החתימה אף הוא ארוך מאוד ותלוי באורך ההודעה

פתרון : במקום לחתום על ההודעה המקורית, חותמים על טביעת אצבע (Digest) של ההודעה (שהיא הרבה יותר קצרה מההודעה המקורית).

1

מועדון הלינוקס החיפאי

יצירת “טביעת אצבע”

כל הזכויות שמורות © All rights reserved

נרצה כי יצירת טביעת האצבע של ההודעה תהיה בטוחה. השאלה היא מה המובן של בטוח בהקשר שלנו.

דרישות:

בהנתן הודעה עם "טביעת אצבע" קשה למצוא הודעה נוספת בעלת אותה "טביעת אצבע"

קשה למצוא שתי הודעות בעלות אותה "טביעת אצבע"

1

מועדון הלינוקס החיפאי

פונקציות חד כיווניות

כל הזכויות שמורות © All rights reserved

פונקציה (y=f(x היא חד-כיוונית, אם:

f קלה לחישוב: בהנתן x, קל לחשב את (y=f(x

f קשה להיפוך: בהינתן y, קשה למצוא x שמקיים: (y=f(x

שימו לב כי פירוש הביטוי "קשה להיפוך" הוא שקשה למצוא מקור 'x כלשהו עבור ערך y נתון (ולאו דווקא את ערך x המקורי).

קיומן של פונקציות חד-כיווניות הינה שאלה פתוחה. ידוע כי אם קיימות פונקציות כאלו אזי P≠NP. ההפך אינו בהכרח נכון.

1

מועדון הלינוקס החיפאי

פונקציות תמצות (hash) קריפטוגרפיות

כל הזכויות שמורות © All rights reserved

פונקציה (h(x תקרא פונקציית תמצות קריפטוגרפית אם היא מקיימת את התכונות הבאות:

כיווץ: אורך הפלט הינו קבוע (על אף שאורך הקלט משתנה)

חד כיווניות (One Way)

חסרת התנגשות (Collision Free): קשה למצוא שתי הודעות בעלות אותו digest.

1

Source
Space

{0,1}*

Target
Space

{0,1}c

מועדון הלינוקס החיפאי

התקפות על פונקציות תמצות

כל הזכויות שמורות © All rights reserved

ישנן שלוש התקפות אפשריות על פונקציות תמצות:

מציאת התנגשות – מציאת זוג הודעות M1

ו-M2 כך ש-(h(M1)=h(M2

מציאת התנגשות שניה – בהנתן הודעה M מוצאים הודעה 'M כך ש-('h(M)=h(M

מציאת מקור – בהנתן y צריך למצוא M כך

ש-h(M)=y

ההתקפות שהתפרסמו בקיץ האחרון מצאו התנגשות בפונקציות התמצות MD5 ו-SHA-0.

1

מועדון הלינוקס החיפאי

חתימה דיגטלית עם פונק' תמצות

כל הזכויות שמורות © All rights reserved

כעקרון, אין שינוי בהגדרות הפורמליות שהשתמשנו בהן קודם. הרי ניתן להניח שאלגוריתם החתימה לוקח את ההודעה M מפעיל עליה את פונקציית התמצות (h(x, ולאחר מכן חותם תוך שימוש בחתימה כרגיל.

הבדיקה גם היא לא משתנה באופן עקרוני. כחלק מאלגוריתם הבדיקה אנו מחשבים את (h(M וממשיכים כרגיל.

עם זאת, מטעמי נוחות, נכתוב את הפונקציות הנ”ל בצורה מפורשת. נגדיר את 'S ואת 'V שמשתמשות ב-S וב-V ובפונקציית תמצות (h(x:

S'(M,PrU) = S (h(M),PrU) = sig

V'(M,sig,PubU) = V(h(M),sig,PubU)

1

מועדון הלינוקס החיפאי

תכונות של פונקציות תמצות בחתימות

כל הזכויות שמורות © All rights reserved

נרצה שהוספת פונקציית התמצות לא תפגע בבטיחות החתימה. כלומר, שעדיין יהיה קשה לייצר זוגות של הודעות וחתימות שיעברו את אלגוריתם הבדיקה, ללא ידיעת המפתח הסודי PrU.

הבעיה העיקרית היא שפונקציות תמצות עלולות להכניס התנגשויות לחתימה. זוג הודעות (M1,M2) יקרא מתנגש אם (h(M1)=h(M2. במקרה שכזה, חתימה לגיטמית Sig על הודעה M1 היא גם חתימה לגיטמית על M2.

שימו לב כי דרשנו שקשה יהיה למצוא התנגשויות, אך בהכרח יש כאלה (עקרון שובך היונים).

1

מועדון הלינוקס החיפאי

פרדוקס יום ההולדת

כל הזכויות שמורות © All rights reserved

מהו מספר האנשים שצריכים להיות בחדר בכדי שבסיכוי גדול מ0.5-, יהיה בחדר איש שיום ההולדת שלו נופל בתאריך זהה לשלי? 183.

מה מספר האנשים שצריכים להיות בחדר בכדי שבסיכוי גדול מ0.5-, יהיו ביניהם שניים שיום ההולדת שלהם באותו תאריך? 23.

דרך פשוטה אחת להצדיק את ה”פרדוקס” היא בכך שיש 253=2/(22*23) זוגות של אנשים בין 23 האנשים, ולכן ההסתברות של זוג מסוים להיות בעל אותו יום הולדת, גדולה מחצי.

1

מועדון הלינוקס החיפאי

פרדוקס יום ההולדת ופונקציות תמצות

כל הזכויות שמורות © All rights reserved

כאשר חותמים על הודעה m, חותמים בעצם על כל ההודעות 'm עבורן ('h(m)=h(m.

פונקציות תמצות קריפטוגרפיות צריכות לקיים את התכונה הבאה: בהינתן הודעה m, קשה מעשית למצוא הודעה 'm כך ש-('h(m)=h(m.

אבל: הרבה יותר קל למצוא מראש שתי הודעות m1 ו-m2, כך ש-(h(m1)=h(m2.

כל פונקציית תמצות קריפטוגרפית חשופה להתקפת יום ההולדת.

1

מועדון הלינוקס החיפאי

מסקנה

כל הזכויות שמורות © All rights reserved

מכיוון שפרדוקס יום ההולדת משפיע על כל פונקציית תמצות שהיא, יש צורך שהפרדוקס לא יפגע בבטיחות.

כדי למצוא התנגשות כאשר אורך הפלט של הפונקציה הוא n סיביות, צריך לנסות בערך 2n/2 הפעלות של פונקציית התמצות.

אם נרצה שתוקף יצטרך להשקיע בסביבות 264 הפעלות של פונקציית התמצות בשביל למצוא התנגשות, הרי שגודל ה-digest שהפונקציה צריכה לפלוט הוא 128 סיביות.

1

מועדון הלינוקס החיפאי

דוגמאות לפונקציות תמצות

כל הזכויות שמורות © All rights reserved

MD4 – הייתה נפוצה בעבר, עד שנמצאה התנגשות. פלט – 128 סיביות.

MD5 – שיפור של MD4, סטנדרט באינטרנט. פלט – 128 סיביות – נמצאה התנגשות לא מזמן.

SHA-1 – שיפור של MD4. נוצרה ע"י NSA עבור NIST לשמש כסטנדרט בארה"ב. פלט – 160 סיביות – בטיחותה מוטלת בספק.

Tiger – פלט – 192 סיביות.

SHA-224, SHA-256, SHA-384, SHA-512 – סטנדרטים חדשים בארה"ב. פלטיהן באורכים המצויינים (224,256,384,512 סיביות בהתאמה).

1

מועדון הלינוקס החיפאי

Message Authentication Codes (MAC)

כל הזכויות שמורות © All rights reserved

הרעיון: בדומה להצפנה בצופן סימטרי, נניח כי לשני הצדדים A, B שמשתתפים בפרוטוקול יש מפתח סודי k משותף. כדי לאמת שהודעה m הגיעה מאחד מהם, הם יחשבו פונקצייה מסויימת, התלויה ב-k.

כלומר (MAC=f(m,k.

דרישות מן ה-MAC:

ללא ידיעת k לא ניתן לייצר MAC חוקי על הודעה m.

גם אם לתוקף יש סט של הודעות ו-MAC-ים תואמים, הוא איננו מסוגל לייצר זוג חדש של הודעה ו-MAC שאיננו בסט.

לא ניתן לשחזר את המפתח k מתוך הודעה m וה-MAC שלה (וגם לא מסט גדול של הודעות ו-MAC).

1

מועדון הלינוקס החיפאי

Message Authentication Codes (MAC)

כל הזכויות שמורות © All rights reserved

אם A מקבל הודעה יחד עם ה-MAC אותו B חישב על ההודעה בעזרת המפתח הסודי, והאימות של ה-MAC מצליח, A יודע בוודאות שההודעה נשלחה מ-B, ושהיא לא שונתה בדרך.

בניגוד לחתימה דיגיטלית, במקרה זה A לא יכול לטעון בבית משפט ש-B שלח לו את ההודעה, מכיוון ש-A עצמו גם מסוגל לייצר את ה-MAC.

לכן MAC לא מספק את תכונת אי ההכחשה.

1

מועדון הלינוקס החיפאי

MAC - המשך

כל הזכויות שמורות © All rights reserved

כלומר MAC הוא פרימטיב סימטרי (משמע מבוסס על מפתח סודי), שמספק שתי תכונות:

אימות

שלמות

MAC איננו מספק Non-repudiation (אי הכחשה).

קיימים שלושה סוגים של MACs:

מבוססי פונקציית תמצות

מבוססי צופן בלוקים

מבוססי צופן שטף

1

מועדון הלינוקס החיפאי

MAC מבוסס פונקציות תמצות

כל הזכויות שמורות © All rights reserved

הרעיון: מתמצתים את ההודעה m והמפתח הסודי k ביחד.

דוגמאות (h היא פונקציית תמצות):

Keyed MAC : MAC = h(k,m,k)

HMAC : MAC = h(h XOR opad, h(k XOR ipad, m))

ipad ו-opad הם קבועים של HMAC.

תכונות:

מספק שלמות (עפ”י הגדרת פונקציית תמצות קריפטוגרפית, קשה למצוא שתי הודעות שתתמפנה אל אותו הערך).

מבצע זיהוי משתמש (ע"י הוספת מפתח סודי לפונקציית התמצות).

1

מועדון הלינוקס החיפאי

MAC מבוסס צפני בלוקים

כל הזכויות שמורות © All rights reserved

הרעיון הוא לנצל את העובדה שללא ידיעת המפתח לא ניתן להצפין מידע.

דוגמא נפוצה ל-MAC מבוסס על צופן בלוקים, הוא CBC-MAC. בשיטה זו הבלוק האחרון של הצפנה ב- CBC mode של ההודעה משמש כ-MAC. כלומר השולח מצפין את ההודעה m תחת המפתח המשותף k תוך שימוש בצופן בלוקים מוסכם וידוע במוד פעולה של CBC. הבלוק האחרון המתקבל בהצפנה – נשלח לצד השני, כעדות לשלמות המידע.

ל-CBC-MAC יש מספר בעיות אבטחה, המאפשרות לייצר הודעה עם MAC גם ללא ידיעת המפתח. עם זאת, הידיעה היא חסרת משמעות (בסיכוי גבוה).

1

מועדון הלינוקס החיפאי

ניהול מפתחות,
Public Key Infrastructure

מפתחות קריפטוגרפיים

כל הזכויות שמורות © All rights reserved

בחיים ישנה ההנחה כי המפתחות הקריפטוגרפיים שלנו הם “טובים”:

נוצרו באופן אקראי טוב (מפתחות סימטריים הוגרלו באקראי באופן בלתי תלוי, מפתחות אסימטריים נוצרו בתהליכים דומים).

משמשים לצרכים שנקבעו (מפתח MAC משמש ל-MAC ולא להצפנה בצופן בלוקים), כמו כן מומלץ להשתמש במפתחות שונים לכל צורך.

אורכם גדול דיו כדי להיות מוגנים בפני סוגי התקפות שונים (לדוגמא, חיפוש ממצה).

1

מועדון הלינוקס החיפאי

תכונות של מפתח קריפטוגרפי

כל הזכויות שמורות © All rights reserved

לכל מפתח קריפטוגרפי מספר תכונות חשובות:

אורך המפתח תלוי ב:

סוג האלגוריתם - צופן סימטרי, MAC, צופן פומבי, או אלגוריתם חתימה דיגטלית

סוג המידע המוצפן - ארוך יותר ככל שהמידע יותר סודי

זמן החיים של המידע – כמה זמן המידע צריך להשמר סודי/חתום

אורך חיים

משך הזמן בו המפתח בשימוש או כמות המידע המוצפן באמצעותו

תלוי באורך החיים של המידע המוגן, והנזק שיגרם במקרה של חשיפה

1

מועדון הלינוקס החיפאי

ניהול מפתחות קריפטוגרפיים

כל הזכויות שמורות © All rights reserved

את המפתחות הקריפטוגרפיים יש לנהל בצורה בטוחה ואמינה:

ייצור בטוח

מפתחות אקראיים לחלוטין

שימוש באמצעים פיסיים לייצור

אחסון בטוח

שמירת המפתחות כך שלא יחשפו (רכיב נפרד)

עדיף שהרכיב הפיסי לייצור ישמש גם לשמירה

הפצת מפתחות (נראה מיד)

החלפת מפתחות סימטריים בין אנשים המעוניינים לתקשר באופן בטוח

הפצת מפתחות אסימטריים (ציבוריים) לצורכי הצפנה אסימטרית וחתימות

1

מועדון הלינוקס החיפאי

ניהול מפתחות קריפטוגרפיים

כל הזכויות שמורות © All rights reserved

עדכון מפתחות

תוקפם של מפתחות יכול לפוג, ואז יש צורך לעדכנם

המפתח הציבורי צריך להיות כזה שניתן לבצע לו Revocation – רישום כמפתח שאיננו חוקי יותר, אף על פי שהוא עדיין בתקופת הקיום החוקית שלו (לדוגמא, המפתח הפרטי נחשף בטעות)

זיהוי בעלי המפתח הציבורי (התקפות התחזות ופלגיאט)

1

מועדון הלינוקס החיפאי

אלגוריתם הסכמה על מפתחות

כל הזכויות שמורות © All rights reserved

נתונים שני אנשים A ו-B המעוניינים להסכים על מפתח סודי (סימטרי) תוך שימוש בערוץ פומבי בלבד.

דרך אפשרית: הצפנת המפתח הסימטרי הסודי על ידי RSA ושליחתו בערוץ הפומבי (ניתן להצפין תחת כל פונקציית הצפנה פומבית בטוחה) – השיטה שמתבצעת ב-PGP.

דרך נוספת: אלגוריתם יעודי להחלפת מפתחות – שיטת Diffie-Hellman

1

מועדון הלינוקס החיפאי

אלגוריתם Diffie-Hellman להסכמה על מפתח סימטרי משותף

כל הזכויות שמורות © All rights reserved

אלגוריתם Diffie-Hellman הוצע בשנת 1977 לצורך יצירת מפתח סודי משותף תוך שימוש בערוץ פומבי.

לכל אחד מהצדדים מפתח ציבורי ומפתח פרטי מתאים.

כל אחד מהצדדים מחשב את המפתח הסודי המשותף תוך שימוש במפתח הפרטי שלו, ובמפתח הציבורי של הצד השני.

1

מועדון הלינוקס החיפאי

אלגוריתם Diffie-Hellman (המשך)

כל הזכויות שמורות © All rights reserved

יהי p מספר ראשוני ויהי g יוצר של *Zp, החבורה הכפלית של Zp. הפרמטרים g ו-p ידועים לכל משתמשי המערכת.

המפתחות:

1

בוב

x

gx (mod p)

אליס

y

gy (mod p)

המפתח הפרטי

המפתח הפומבי

מועדון הלינוקס החיפאי

אלגוריתם Diffie-Hellman (המשך)

כל הזכויות שמורות © All rights reserved

1

אליס

בוב

1)

x,gx(mod p)

y,gy(mod p)

2)

gx(mod p)

gy(mod p)

3)

gyx(mod p)

gxy(mod p)

מועדון הלינוקס החיפאי

אלגוריתם Diffie-Hellman - רקע

כל הזכויות שמורות © All rights reserved

ההנחה המובלעת מאחורי אלגוריתם Diffie-Hellman היא שבהנתן gx,p,g ו-gy קשה לחשב מתוכם את gxy (כל החישובים הם mod p).

בעיה זו (בעיית DH) קשורה לבעיית ה-DLOG (הלוגריתם הדיסקרטי): בהנתן g,p,gx מצא את x.

כמו בעיית RSA (ובעיית הפירוק לגורמים) גם בעיות אלה נחשבות קשות, ועד היום אין אלגוריתמים טובים לפתרונן.

1

מועדון הלינוקס החיפאי

אלגוריתם Diffie-Hellman - אזהרות

כל הזכויות שמורות © All rights reserved

שימו לב כי אלגוריתם Diffie-Hellman משמש אך ורק להסכמה על מפתח סימטרי משותף בין שני משתתפים.

האלגוריתם איננו יכול לשמש עבור:

1. הצפנת מפתח פומבי

2. חתימות דיגטליות

3. כל דבר שאיננו הסכמה על מפתחות

הערה: שימו לב כי שני אנשים המשתמשים תמיד באותם מפתחות פומביים (ופרטיים מתאימים) יסכימו תמיד על אותו מפתח משותף.

1

מועדון הלינוקס החיפאי

Public Key Infrastructure (PKI)

כל הזכויות שמורות © All rights reserved

PKI הינה תשתית להעברה, פרסום ואימות של מפתחות ציבוריים.

המפתחות הפומביים בדרך כלל מפורסמים בעזרת סרטיפיקטים.

הגדרה של PKI צריכה להכיל הגדרות של התהליכים הבאים:

מתן סרטיפיקט (certification): מי מנפיק סרטיפיקט למי, תהליך ההנפקה, ואיפה הסרטיפיקט שמור.

אימות מפתח פומבי: כיצד מוצאים סרטיפיקטים של ישויות במערכת וכיצד מאמתים סרטיפיקט (האם הוא תקף).

ביטול הסרטיפיקט.

1

מועדון הלינוקס החיפאי

פרוטוקולי הזדהות קריפטוגרפיים

כל הזכויות שמורות © All rights reserved

ראינו קודם לכן, כי יש פעולות שרק קבוצה מסוימת של אנשים מסוגלת לבצע – לדוגמא, חתימה דיגטלית ניתנת לביצוע רק על ידי מחזיק המפתח הפרטי.

ניתן לנצל תכונות אלה לצורך זיהוי – אם אנחנו מעוניינים לבדוק האם אדם מסוים הוא עצמו (דרך האינטרנט), נוכל לשלוח לו “אתגר” קריפטוגרפי שרק הוא ידע לפתור.

רעיון זה נמצא בבסיסם של לא מעט פרוטוקולי בקרת כניסה – Kerberos, PPTP, SRP, EKE ואפילו בצורה מסוימת ב-SSH.

1

מועדון הלינוקס החיפאי

הוכחות באפס מידע

כל הזכויות שמורות © All rights reserved

הרעיון הבסיס מאחורי הוכחות באפס מידע (Zero Knowledge Proof) הוא העובדה כי ניתן להוכיח טענה מסוימת ללא חשיפת ההוכחה עצמה.

לדוגמא, כאשר מוכיחים טענה מתמטית מסוימת, אנחנו מצרפים הוכחה כך שכל אדם יוכל לבדוק את ההוכחה.

בחלק מן המקרים, ניתן לתת הוכחה “הסתברותית”, כזו שתשכנע אותנו בסיכוי נורא גבוה, אך לא תחשוף את דרך ההוכחה.

לדוגמא, הקוסם הודיני טען שהוא מסוגל להשתחרר מכל קשר שהוא. במשך הרבה מאוד פעמים הוא הוכיח יכולת זו, בלי לחשוף את צורת פעולתו.

1

מועדון הלינוקס החיפאי

הוכחות באפס מידע (המשך)

כל הזכויות שמורות © All rights reserved

אפשר להגדיר את מחלקת השפות שניתנות להוכחה באפס מידע. מחלקה זו כוללת בתוכה את NP, ולכן ניתן להוכיח כי אנחנו יודעים אלגוריתם הפותר את SAT, גם ללא חשיפתו.

מקרה פרטי של הוכחות באפס מידע, הוא הוכחות מקרה באפס מידע (zero knowledge arguments). במקרה זה, אנחנו מוכיחים ידיעת פתרון אחד מסוים לבעיה, מבלי לחשוף את אותו פתרון.

לדוגמא, בעיית ה-3-צביעה של גרף היא בעייה NP-שלמה. בהנתן גרף ושלוש צביעה שלו, ניתן להוכיח את הידיעה הזו, ללא חשיפת ה-3-צביעה עצמה.

1

מועדון הלינוקס החיפאי

מקורות נוספים

כל הזכויות שמורות © All rights reserved

אתר הקורס קריפטולוגיה מודרנית (236506) - http://www.cs.technion.ac.il/~cs236506

הספר – Cryptography: Theory and Practice (מהדורה ראשונה!) מאת D.R. Stinson.

הספר – The Code Breaker מאת David Kahn.

אתר International Association of Cryptlogic Research http://www.iacr.org.

לא להציץ ב-sci.crypt! איכות הדיון והמידע המפורסמים שם היא נמוכה עד שלילית.

הספר של ברוס שנייר (Applied Cryptography) הוא בעייתי עקב ריבוי שגיאות. עם זאת אם מתעלמים מכל האספקטיים הטכניים, הוא סביר למדי.

1

מועדון הלינוקס החיפאי

מבוא לקריפטוגרפיה - מועדון הלינוקס החיפאי

מיהם עליזה, בני וחווה?

2004-02-17T14:14:28